题意
维护数据结构，支持以下操作：
1.插入 2.把所有数的权值改变一个数 3.删除所有小于Min的数
题解
平衡树维护，2操作视为Min的上下浮动，插入时-delta即可
调试记录
rotate没有pushup
删除的时候ans可能不止+11
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
using namespace std;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int Q, Min, delta = 0, cnt = 0, ans = 0, rt = 0;
struct T{
struct A{
int son[2], v, sz, lnk, rd;
}a[maxn * 40]; int tot;
T(){tot = 0;}
void pushup(int cur){
a[cur].sz = S(0).sz + S(1).sz + a[cur].v;
}
void rotate(int &cur, int d){
int k = a[cur].son[d ^ 1];
a[cur].son[d ^ 1] = a[k].son[d];
a[k].son[d] = cur;
pushup(cur); pushup(k);
cur = k;
}
void ins(int &cur, int x){
if (!cur){
cur = ++tot;
a[cur].lnk = x;
a[cur].rd = rand();
a[cur].v = a[cur].sz = 1;
return;
}
if (a[cur].lnk == x){
a[cur].v++;
a[cur].sz++;
return;
}
int d = a[cur].lnk < x;
ins(a[cur].son[d], x);
if (S(d).rd > a[cur].rd) rotate(cur, d ^ 1);
a[cur].sz = S(0).sz + S(1).sz + a[cur].v;
}
void del(int &cur, int x){
if (!cur) return;
if (a[cur].lnk > x) del(a[cur].son[0], x);
else if (a[cur].lnk < x) del(a[cur].son[1], x);
else{
if (!a[cur].son[0] && !a[cur].son[1]){
ans += a[cur].v;
a[cur].sz = 0; a[cur].v = 0; cur = 0;
}
else if (!a[cur].son[0] && a[cur].son[1]){
rotate(cur, 0);
del(a[cur].son[0], x);
}
else if (a[cur].son[0] && !a[cur].son[1]){
rotate(cur, 1);
del(a[cur].son[1], x);
}
else{
int d = S(0).rd > S(1).rd;
rotate(cur, d);
del(a[cur].son[d], x);
}
}
a[cur].sz = S(0).sz + S(1).sz + a[cur].v;
}
int find(int cur, int x){
if (!cur) return 0;
if (S(0).sz >= x) return find(a[cur].son[0], x);
else if (S(0).sz + a[cur].v >= x) return a[cur].lnk;
else return find(a[cur].son[1], x - S(0).sz - a[cur].v);
}
int pre(int cur, int x){
if (!cur) return -INF;
if (a[cur].lnk >= x) return pre(a[cur].son[0], x);
return max(a[cur].lnk, pre(a[cur].son[1], x));
}
}t;
int main(){
srand(unsigned(time(0)));
scanf("%d%d", &Q, &Min);
while (Q--){
char opt[5]; int k;
scanf("%s%d", opt, &k);
if (opt[0] == 'I'){
if (k >= Min) t.ins(rt, k - delta), ++cnt;
}
if (opt[0] == 'A') delta += k;
if (opt[0] == 'S') delta -= k;
if (opt[0] == 'F'){
if (k > cnt - ans) puts("-1");
else printf("%d\n", t.find(rt, cnt - ans - k + 1) + delta);
}
while (t.pre(rt, Min - delta) != -INF){
t.del(rt, t.pre(rt, Min - delta));
}
} printf("%d\n", ans);
return 0;
}